class Solution {
	vector<int> ret; // 要返回的数组
	vector<int> index; // nums中元素的原始下标
	vector<int> tmp_nums;
	vector<int> tmp_index; // 和nums里的元素绑定一起移动
public:
	vector<int> countSmaller(vector<int>& nums) {
		int n = nums.size();
		ret.resize(n);
		index.resize(n);
		tmp_nums.resize(n);
		tmp_index.resize(n);
		for (int i = 0; i < n; ++i)
		{
            index[i] = i; // 初始化下标数组
        }
		mergeSortCnt(nums, 0, n - 1);
		return ret;
	}
 
	void mergeSortCnt(vector<int>& nums, int left, int right)
	{
		if (left >= right)
			return;
		int mid = (left + right) >> 1;
		mergeSortCnt(nums, left, mid);
		mergeSortCnt(nums, mid + 1, right);
 
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right)
		{
			if (nums[cur1] > nums[cur2])
			{
				ret[index[cur1]] += (right - cur2 + 1);
				tmp_nums[i] = nums[cur1];
				tmp_index[i++] = index[cur1++];
			}
			else
			{
				tmp_nums[i] = nums[cur2];
				tmp_index[i++] = index[cur2++];
			}
		}
		while (cur1 <= mid)
		{
			tmp_nums[i] = nums[cur1];
			tmp_index[i++] = index[cur1++];
		}
		while (cur2 <= right)
		{
			tmp_nums[i] = nums[cur2];
			tmp_index[i++] = index[cur2++];
		}
		for (int j = left; j <= right; ++j)
		{
			nums[j] = tmp_nums[j - left];
			index[j] = tmp_index[j - left];
		}
	}
};